#!/usr/bin/env python
# -*- coding:utf-8 -*-

"""
需求：
1、 一个数字矩阵。
2、 行动时选择一行或一列，使其中的每个数字减 1 。
3、 当有一个数字减为 0 时，增加一次行动的机会。
4、 求使指定位置的数字减为 0 时的步骤。
"""

# 数字矩阵，求使 boats[1][1] 减为 0 的步骤
boats = [
	[2, 3, 1],
	[3, 5, 2],
	[2, 3, 2]
]
# 初始行动次数
boom = 1


# 深层复制数组
def copy(boats):
	copy_boats = []
	for list in boats:
		copy_boats.append(list[:])
	return copy_boats


# 打印矩阵
def log():
	print('-' * 20)
	for boats_row in boats:
		print(boats_row)
	print('boom: ', boom)


# 行减一
def left_boom(row, boats, boom):
	boom -= 1
	for i in range(3):
		if boats[row][i] > 0:
			boats[row][i] -= 1
			if boats[row][i] == 0:
				boom += 1
	return boats, boom


# 列减一
def right_boom(col, boats, boom):
	boom -= 1
	for i in range(3):
		if boats[i][col] > 0:
			boats[i][col] -= 1
			if boats[i][col] == 0:
				boom += 1
	return boats, boom


# 行动类，封装行动的方法
class Action(object):
	def __init__(self, fx, index):
		self.fx = fx
		self.index = index
		self.using = False

	# 执行行动
	def do(self, boats, boom):
		if self.fx == 'L':
			return left_boom(self.index, boats, boom)
		elif self.fx == 'R':
			return right_boom(self.index, boats, boom)


# 生成行动方案数组，元素为行动类对象
def get_action(boats, boom):
	actions = []
	action_set = set()
	for row in range(3):
		for col in range(3):
			if 0 < boats[row][col] <= boom:
				action_set.add('L' + str(row))
				action_set.add('R' + str(col))
	for action in action_set:
		actions.append(Action(action[0], int(action[1])))
	return actions


steps = []		# 步骤
win = False		# 是否达成目标


# 递归遍历所有步骤
def play(boats, boom):
	global steps, win
	# 若中心元素为0，则完成
	if boats[1][1] == 0:
		win = True
		return
	# 获取行动方案，若为空，则退出
	actions = get_action(boats, boom)
	if not actions:
		return
	# 循环所有行动方案
	for action in actions:
		next_boats, next_boom = action.do(copy(boats), boom)
		# 递归
		play(next_boats, next_boom)
		# 如果达成目标，将该行动插入到数组
		if win:
			steps.insert(0, action)
			return


play(boats, boom)
for step in steps:
	boats, boom = step.do(boats, boom)
	log()
	print(step.fx, step.index)